package main

import (
	"fmt"
	"go-study/algorithm/standard"
)

// 如何在二叉排序树中找出第一个大于中间值的节点

func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7}
	root := standard.ArrayToTree(data, 0, len(data)-1)
	fmt.Println(getNode(root).Data)
}

func getNode(root *standard.BNode) *standard.BNode {
	max := getMaxNode(root).Data.(int)
	min := getMinNode(root).Data.(int)
	mid := (max + min) / 2

	var result *standard.BNode
	for root != nil {
		if root.Data.(int) <= mid {
			root = root.RightChild
		} else {
			result = root
			root = root.LeftChild
		}
	}

	return result
}

func getMaxNode(node *standard.BNode) *standard.BNode {
	if node == nil {
		return node
	}

	current := node
	for current.RightChild != nil {
		current = current.RightChild
	}

	return current
}

func getMinNode(node *standard.BNode) *standard.BNode {
	if node == nil {
		return node
	}

	current := node
	for current.LeftChild != nil {
		current = current.LeftChild
	}

	return current
}
